# 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
#
#  示例 1：
# 输入：nums = [2,2,3,2]
# 输出：3
#
#  示例 2：
# 输入：nums = [0,1,0,1,0,1,99]
# 输出：99
import collections
from typing import List


class Solution:
    def singleNumber3(self, nums: List[int]) -> int:
        pass

    def singleNumber2(self, nums: List[int]) -> int:
        """
        逐位求结果的二进制
        只有一个数出现一次(将其称为【结果】)
        【结果】的第 i 个二进制位（i 从 0 开始编号），它可能为 0 或 1。
        对于数组中非答案的元素，每一个元素都出现了 3 次，对应着第 i 个二进制位的 3 个0 或 3 个 1，
        无论是哪一种情况，它们的和都是 3 的倍数（即和为 0 或 3）。
        所以结果的第 i 个二进制位为 数组中所有元素的第 i 个二进制位之和除以 3 的余数
        :param nums:
        :return:
        """
        res = 0
        for i in range(32):
            tmpBitTotal = sum(num >> i & 1 for num in nums)  # 数组中所有元素的第 i 个二进制位之和
            if tmpBitTotal % 3 == 1:
                if i == 31:  # 对最高位进行特殊判断
                    res -= (1 << i)
                else:
                    res |= (1 << i)
        return res

    def singleNumber1(self, nums: List[int]) -> int:
        dic = collections.Counter(nums)
        for k, v in dic.items():
            if v == 1:
                return k
        return 0

    def singleNumber(self, nums: List[int]) -> int:
        return self.singleNumber2(nums)


if __name__ == "__main__":
    nums = [0, 1, 0, 1, 0, 1, 99]
    print(Solution().singleNumber(nums))
